/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: mac
 * Date: 2022-08-26
 * Time: 21:06
 */
public class KMPDemo {
    /**
     * BF算法
     * @param str 主串
     * @param sub 子串
     * @param pos 从子串的pos位置进行匹配
     * @return 找到子串在主串中下标
     */
    public static int BF(String str, String sub, int pos){
        if (str == null || sub == null) return -1;
        int lenStr = str.length();
        int lenSub = sub.length();
        if (lenStr == 0 || lenSub == 0) return -1;

        if (pos < 0 || pos >= lenSub) return -1;

        int i = pos;//遍历主串
        int j = 0;//遍历子串

        while (i < lenStr && j < lenSub){
            if (str.charAt(i) == sub.charAt(j)){
                i++;
                j++;
            } else {
                i = i - j + 1;
                j = 0;
            }
        }
        if (j >= lenSub){
            return i - j;
        }
        return -1;
    }
    /**
     * KMP算法
     * @param str 主串
     * @param sub 子串
     * @param pos 从子串的pos位置进行匹配
     * @return 找到子串在主串中下标
     */
    public static int KMP(String str, String sub, int pos){
        if (str == null || sub == null) return -1;
        int lenStr = str.length();
        int lenSub = sub.length();
        if (lenStr == 0 || lenSub == 0) return -1;

        if (pos < 0 || pos >= lenSub) return -1;

        int[] next = new int[lenSub];
        //得到next数组
        getNext(sub, next);

        int i = pos;//遍历主串
        int j = 0;//遍历子串

        while (i < lenStr && j < lenSub){
            //j == -1 一开始就匹配失败了
            if (j == -1 || str.charAt(i) == sub.charAt(j)){
                i++;
                j++;
            } else {
                j = next[j];
            }
        }
        if (j >= lenSub){
            return i - j;
        }
        return -1;
    }

    public static void getNext(String sub, int[] next){
        next[0] = -1;
        int i = 1;
        int k = -1;
        while (i < sub.length()) {
            if (k == -1 || sub.charAt(i - 1) == sub.charAt(k)){
                next[i] = k + 1;
                if (sub.charAt(next[i]) == sub.charAt(i)){
                    next[i] = next[next[i]];
                }
                k++;
                i++;
            } else{
                k = next[k];
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(KMP("ababcabcaabbcdeabcdef","abcaabb", 0));
        System.out.println(BF("ababcabcdabcdeabcdef","abcdf", 0));
        System.out.println(BF("ababcabcdabcdeabcdef","ab", 0));
    }
}
